package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    //letcode 300 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence/description/
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int ret = 1;
        for (int i = 0; i < n; i++) dp[i] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = i-1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }

    /**
     * 贪心
     * @param nums
     * @return
     */
    public int lengthOfLIS2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            if (nums[i] > list.get(list.size() - 1)) {
                list.add(nums[i]);
                continue;
            }else {
                int index = find(list,nums[i]);
                list.set(index,nums[i]);
            }
        }
        return list.size();
    }

    private int find(List<Integer> list,int target) {
        int left = 0, right = list.size(), mid = 0;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return left;
    }
}
